package com.jzoffer;

/*
 *牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，
 * 写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，
 * 但却读不懂它的意思。例如，“student. a am I”。后来才意识到，
 * 这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。
 * Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
 *
* */
public class ReverseSentences {

    public static void main(String[] args) {
        String str = " inverse student. a am I ";
        String s = reverseSentence(str);
        System.out.println(s);

    }

    public static String reverseSentence(String str){
        if(str == null || str.length() < 2){
            return str;
        }

        char [] temp = str.toCharArray();
        int len = temp.length;
        reverse(temp,0,len - 1);

        // 遍历 找到单词的左右边界 再次反转
        int i = 0;
        while (i < len ){
            int start = findStart(i,temp);
            if(start >=  len){
                break;
            }
            int end = findEnd(start,temp);
            reverse(temp,start,end);
            i = end + 1;
        }

        str = new String(temp,0,len);

        return str;
    }

    // 找单词的开头
    private static int findStart(int i,char[] temp){

        while (i < temp.length && temp[i] == ' '){
            i++;
        }
        return i;

    }

    // 找单词尾巴
    private static int findEnd(int i,char[] temp){
        while (i < temp.length && temp[i] != ' '){
            i++;
        }
        return i - 1;
    }

    // 字符串反转
    private static void reverse(char[] ch,int start,int end){
        if(start >= end){
            return;
        }
        while (start < end){
            char t = ch[start];
            ch[start] = ch[end];
            ch[end] = t;
            start++;
            end--;
        }
    }

}
